package com.darrenchan.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-02-29 20:39
 */
//arthas阿里工具
class Point {
    int x;
    int y;

    Point() {
        x = 0;
        y = 0;
    }

    Point(int a, int b) {
        x = a;
        y = b;
    }
}

public class QLint434 {
    public List<Integer> numIslands2(int n, int m, Point[] operators) {
        List<Integer> results = new ArrayList<>();

        if(operators == null || operators.length == 0) {
            return results;
        }

        int[][] grid = new int[n][m];
        UnionFind2 uf = new UnionFind2(n * m);
        uf.setLen(0);
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, -1, 0, 1};

        for (int i = 0; i < operators.length; i++) {
            int x = operators[i].x;
            int y = operators[i].y;

            if(grid[x][y] == 1) {
                results.add(uf.query());
                continue;
            }

            uf.setLen(uf.query() + 1);
            grid[x][y] = 1;

            for (int j = 0; j < 4; j++) {
                int nx = x + dx[j];
                int ny = y + dy[j];

                if(isValid(n, m, nx, ny) && grid[nx][ny] == 1) {
                    uf.connect(x * m + y, nx * m + ny);
                }
            }

            results.add(uf.query());
        }

        return results;
    }

    private boolean isValid(int n, int m, int nx, int ny) {
        return nx >= 0 && nx < n && ny >= 0 && ny < m;
    }
}

class UnionFind2 {
    private int[] father;
    private int cnt;

    public void setLen(int len) {
        this.cnt = len;
    }

    private int find(int x) {
        if (x == father[x]) {
            return x;
        }

        return father[x] = find(father[x]);
    }

    public UnionFind2(int n) {
        father = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            father[i] = i;
        }
    }

    public void connect(int a, int b) {
        int fatherA = find(a);
        int fatherB = find(b);

        if (fatherA != fatherB) {
            father[fatherA] = fatherB;
            cnt--;
        }
    }

    public int query() {
        return cnt;
    }
}
